package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/merge-nodes-in-between-zeros/'>合并零之间的节点(Merge Nodes in Between Zeros)</a>
 * <p>给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。</p>
 * <p>对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。</p>
 * <p> 返回修改后链表的头节点 head 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [0,<a color='green'>3</a>,<a color='green'>1</a>,0,<a color='red'>4</a>,<a color='red'>5</a>,<a color='red'>2</a>,0]
 *      输出：[4,11]
 *      解释：
 *          上图表示输入的链表。修改后的链表包含：
 *          - 标记为绿色的节点之和：3 + 1 = 4
 *          - 标记为红色的节点之和：4 + 5 + 2 = 11
 *
 * 示例 2：
 *      输入：head = [0,<a color='green'>1</a>,,0,<a color='red'>3</a>,0,<a color='blue'>2</a>,<a color='blue'>2</a>,0]
 *      输出：[1,3,4]
 *      解释：
 *          上图表示输入的链表。修改后的链表包含：
 *          - 标记为绿色的节点之和：1 = 1
 *          - 标记为红色的节点之和：3 = 3
 *          - 标记为蓝色的节点之和：2 + 2 = 4
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *     <li>列表中的节点数目在范围 [3, 2 * 10^5] 内</li>
 *     <li>0 <= Node.val <= 1000</li>
 *     <li>不 存在连续两个 Node.val == 0 的节点</li>
 *     <li>链表的 开端 和 末尾 节点都满足 Node.val == 0</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/9 11:10
 */
public class LC2181MergeNodesInBetweenZeros_M {

    static class Solution {
        public ListNode mergeNodes(ListNode head) {
            ListNode ans = head;
            int sum = 0;
            for (ListNode temp = head.next; temp != null; temp = temp.next) {
                sum += temp.val;
                if (temp.val == 0) {
                    ans.val = sum;
                    // 断开后面的
                    if (temp.next == null) {
                        ans.next = null;
                    } else {
                        ans = ans.next;
                        sum = 0;
                    }
                }
            }
            return head;
        }
    }


    public ListNode mergeNodes(ListNode head) {

        ListNode currNode = head;
        ListNode nextNode = currNode.next;
        while (nextNode.next != null) {
            // if成立说明到netxNode到了下一组的头节点。修改currNode的`next`指针进入下一组
            if (nextNode.val == 0) {
                currNode.next = nextNode;
                currNode = currNode.next;
            } else {
                // 当前组的val进行求和
                currNode.val = currNode.val + nextNode.val;
            }
            nextNode = nextNode.next;
        }
        currNode.next = null;
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(3);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(0);
        head.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next.next.next = new ListNode(0);

        Solution solution = new Solution();
        ListNode node = solution.mergeNodes(head);
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }
}
